home *** CD-ROM | disk | FTP | other *** search
/ PsL Monthly 1993 December / PSL Monthly Shareware CD-ROM (December 1993).iso / prgmming / dos / c / flxlstc.exe / FLEXLIST.C < prev    next >
C/C++ Source or Header  |  1990-12-05  |  23KB  |  1,031 lines
  1. /*
  2.  
  3.     flexlist.c
  4.     10-4-90
  5.     Homogeneous-heterogeneous 
  6.     hybrid stack-queue-list-array generic class.
  7.     ANSI C
  8.  
  9.     Copyright 1990
  10.     John W. Small
  11.     All rights reserved
  12.  
  13.     PSW / Power SoftWare
  14.     P.O. Box 10072,
  15.     McLean, Virginia 22102 8072
  16.     (703) 759-3838
  17.  
  18. */
  19.  
  20.  
  21. #include <flexlist.h>    /*  <stddef.h>  size_t  */
  22. #include <stdlib.h>     /*  malloc(), free()  */
  23. #include <string.h>    /*  memcpy(), memset()  */
  24.  
  25.  
  26. /*  String variant FlexNode virtual functions  */
  27.  
  28. /*
  29.     FNnew() is called by FlexList functions (primitives)
  30.     that need to allocate new variant length FlexNodes,
  31.     e.g. FLpushD(), FLinsQD(), FLinsD(), FLinsSortD().
  32.     A pointer to the data to be placed in the new node
  33.     is passed to FNnew().  Your FNnew() function must
  34.     decide how large that data is and allocate a new 
  35.     FlexNode big enough to hold that data, i.e.
  36.  
  37.     FlexN N = malloc(sizeof(FlexNode) + 
  38.         sizeofYourData - 1).
  39.  
  40.     Your FNnew() function must also copy that data to
  41.     the new node.  "D" is never NULL!
  42.  
  43.     Please note that FNnew() could call a known function
  44.     pointer (function) in the data to determine its size.
  45.     It could also call another function to copy/
  46.     initialize the FlexNode data area from the data.
  47.     Data that contains its own functions for interfacing 
  48.     with itself are called objects.  Thus FlexLists can 
  49.     be made to hold polymorphic objects via the 
  50.     virtual function table functionology.
  51.  
  52.     Study all four virtual functions FNnew(), FNwrite(),
  53.     FNread(), and FNdestruct() for strings and how they
  54.     are called by the various FlexList functions to get
  55.     a better understanding of variant FlexLists.
  56. */
  57.  
  58. static FlexN FNnewStr(const void *D)
  59. {
  60.     FlexN N;
  61.     size_t i;
  62.  
  63.     for (i = 0; ((char *)D)[i++]; /* no reinit */)
  64.         /* null statement */;
  65.     if ((N = malloc(sizeof(FlexNode)+i-1)) != FlexN0)
  66.         (void) memcpy(N->data,D,i);
  67.     return N;
  68. }
  69.  
  70.  
  71. /*  FNwrite() is called by FLstoreD() to write variant data
  72.     to a variant FlexNode.  Make sure the new data 
  73.     doesn't write pass the end of the old.  FNwrite()
  74.     returns true if the write is successful.  "ND" and
  75.     "D" are never NULL! */
  76.  
  77. static int FNwriteStr(void *ND, const void *D)
  78. {
  79.     char *nd, *d;
  80.     
  81.     nd = (char *) ND;
  82.     d = (char *) D;
  83.     while (*nd)
  84.         if ((*nd++ = *d++) == '\0')
  85.             break;
  86.     return 1;
  87. }
  88.  
  89. /*  FNread() is called by FLtopD(), FLnextD(), 
  90.     FLprevD(), and FLrecallD() to read variant data
  91.     from a variant FlexNode.  FNread() returns true if
  92.     the read is successful.  "ND" and "D" are never 
  93.     NULL!  */
  94.  
  95. static int FNreadStr(const void *ND, void *D)
  96. {
  97.     char *nd, *d;
  98.     
  99.     nd = (char *) ND;
  100.     d = (char *) D;
  101.     while ((*d++ = *nd++) != '\0')
  102.         /* null statement */;
  103.     return 1;
  104. }
  105.  
  106. /*  FNdestruct() is called by FLclear(), FLdelete() via 
  107.     Flclear(), FLpopD(), and FLdelD() to destruct
  108.     variant data in a FlexNode.  Please note that
  109.     references to suballocated memory may be copied
  110.     to the outgoing data structure instead of being
  111.     cloned and then deallocated.  You must keep any
  112.     scheme straight though.  FLclear() always passes
  113.     NULL to the second parameter of FNdestruct() via
  114.     a call to FLpopD(L,0),    however, so any 
  115.     suballocated memory must be freed in that case!
  116.     "ND" is never NULL but "D" can be!  */
  117.  
  118. static int FNdestructStr(void *ND, void *D)
  119. {
  120.     char *nd, *d;
  121.     
  122.     nd = (char *)ND;
  123.     if ((d = (char *)D) != (char *)0) 
  124.         while ((*d++ = *nd++) != '\0')
  125.             /* null statement */;
  126.     return 1;
  127. }
  128.  
  129. /*  Any of the virtual functions can be absent.  The FlexList
  130.     functions that call them will simply return a failure
  131.     indication.  Use FNnew0, FNwrite0, FNread0, and/or
  132.     FNdestruct0 as zero initializers.  */
  133.  
  134. FlexNodeVFT FlexNodeStrVFT = { 
  135.     FNnewStr, FNwriteStr, FNreadStr, FNdestructStr };
  136.  
  137.  
  138. /*  FlexList constructors/destructor - static headers */
  139.  
  140.  
  141. #define FLzero(L) memset((void *)(L),0,sizeof(FlexList)-1)
  142.  
  143. FlexL FLfixed(FlexL L, size_t sizeofNodeData)
  144. {
  145.     if (!L)  
  146.         return L;
  147.     (void) FLzero(L);
  148.     if (!sizeofNodeData || sizeofNodeData 
  149.         > FLmaxSizeofNodeData)
  150.         return FlexL0;
  151.     L->maxNodes = FLmaxMaxNodes;
  152.     L->sizeofNodeData = sizeofNodeData;
  153.     L->sizeofNode = sizeof(FlexNode) 
  154.         + sizeofNodeData - 1;
  155.     L->sorted = 1;
  156.     return L;
  157. }
  158.  
  159. FlexL FLunpack(FlexL L, size_t sizeofCell, 
  160.     unsigned cells, const void *array)
  161. {
  162.     if (!L) 
  163.         return L;
  164.     (void) FLzero(L);
  165.     if ((sizeofCell > FLmaxSizeofNodeData) ||
  166.         !sizeofCell || !cells || !array)
  167.         return FlexL0;
  168.     L->maxNodes = FLmaxMaxNodes;
  169.     L->sizeofNodeData = sizeofCell;
  170.     L->sizeofNode = sizeof(FlexNode) 
  171.         + sizeofCell - 1;
  172.     for (;cells && FLinsQD(L,array); cells--)
  173.         array = (char *) array + sizeofCell;
  174.     return L;
  175. }
  176.  
  177. FlexL FLvariant(FlexL L, FlexNVFT vft)
  178. {
  179.     if (!L)
  180.         return L;
  181.     (void) FLzero(L);
  182.     if (!vft)
  183.         return FlexL0;
  184.     L->maxNodes = FLmaxMaxNodes;
  185.     L->sorted = 1;
  186.     L->vft = vft;
  187.     return L;
  188. }
  189.  
  190. int   FLclear(FlexL L)
  191. {
  192.     while (FLpopD(L,(void *)0))
  193.         /* null statement */;
  194.     if (L) if (!L->nodes)
  195.         return (L->sorted = 1);
  196.     return 0;
  197. }
  198.  
  199. /*  FlexList constructors/destructor - dynamic headers  */
  200.  
  201. /*  FlexList headers are flagged as dynamic if and only if
  202.     FLDdestruct != NULL.  FLDmalloced() is the default
  203.     function pointer whenever one isn't specified.  */
  204. #pragma argsused
  205. /* ARGSUSED */ 
  206. static int FLDmalloced(void *LD)
  207. {    /*  LD is intentionally unused!  */
  208.     return 1;
  209. }
  210.  
  211. static FlexL FLnew(size_t sizeofLocalData, 
  212.     int (*FLDdestruct)(void *LD))
  213. {
  214.     FlexL L;
  215.  
  216.     if (sizeofLocalData > FLmaxSizeofLocalData) 
  217.         return FlexL0;
  218.     L = (FlexL) malloc(sizeof(FlexList) + 
  219.         sizeofLocalData - 1);
  220.     if (L)  {
  221.         (void) FLzero(L);
  222.         if (FLDdestruct)
  223.             L->FLDdestruct = FLDdestruct;
  224.         else
  225.             L->FLDdestruct = FLDmalloced;
  226.     }
  227.     return L;
  228. }
  229.  
  230. FlexL FLfixedNew(size_t sizeofNodeData,
  231.     size_t sizeofLocalData, 
  232.     int (*FLDdestruct)(void *LD))
  233. {
  234.     FlexL L;
  235.  
  236.     if (!sizeofNodeData || sizeofNodeData > 
  237.         FLmaxSizeofNodeData) 
  238.         return FlexL0;
  239.     if ((L = FLnew(sizeofLocalData,FLDdestruct)) 
  240.         != FlexL0)  {
  241.         L->maxNodes = FLmaxMaxNodes;
  242.         L->sizeofNodeData = sizeofNodeData;
  243.         L->sizeofNode = sizeof(FlexNode) 
  244.             + sizeofNodeData - 1;
  245.         L->sorted = 1;
  246.     }
  247.     return L;
  248. }
  249.  
  250. FlexL FLunpackNew(size_t sizeofCell, 
  251.     unsigned cells, const void *array,
  252.     size_t sizeofLocalData,
  253.     int (*FLDdestruct)(void *LD))
  254. {
  255.     FlexL L;
  256.  
  257.     if ((sizeofCell > FLmaxSizeofNodeData) ||
  258.         !sizeofCell || !cells || !array)
  259.         return FlexL0;
  260.     if ((L = FLnew(sizeofLocalData,FLDdestruct)) 
  261.         != FlexL0)  {
  262.         L->maxNodes = FLmaxMaxNodes;
  263.         L->sizeofNodeData = sizeofCell;
  264.         L->sizeofNode = sizeof(FlexNode) 
  265.             + sizeofCell - 1;
  266.         for (;cells && FLinsQD(L,array); cells--)
  267.             array = (char *) array + sizeofCell;
  268.     }
  269.     return L;
  270. }
  271.  
  272. FlexL FLvariantNew(FlexNVFT vft,
  273.     size_t sizeofLocalData,
  274.     int (*FLDdestruct)(void *LD))
  275. {
  276.     FlexL L;
  277.  
  278.     if (!vft) 
  279.         return FlexL0;
  280.     if ((L = FLnew(sizeofLocalData,FLDdestruct)) 
  281.         != FlexL0)  {
  282.         L->maxNodes = FLmaxMaxNodes;
  283.         L->sorted = 1;
  284.         L->vft = vft;
  285.     }
  286.     return L;
  287. }
  288.  
  289. int FLdelete(FlexL *Lptr)
  290. {
  291.     if (!Lptr) 
  292.         return 0;
  293.     if (!(*Lptr)->FLDdestruct) 
  294.         return 0;
  295.     if (!(*((*Lptr)->FLDdestruct))((*Lptr)->data))
  296.         return 0;
  297.     if (!FLclear(*Lptr)) 
  298.         return 0;
  299.     free(*Lptr); 
  300.     *Lptr = FlexL0;
  301.     return 1;
  302. }
  303.  
  304.  
  305. /*  FlexList header functions  */
  306.  
  307. int FLsetMaxNodes(FlexL L, unsigned maxNodes)
  308. {
  309.     if (L)
  310.         if (maxNodes >= L->nodes)  {
  311.             L->maxNodes = maxNodes;
  312.             return 1;
  313.         }
  314.     return 0;
  315. }
  316.  
  317. int FLsetCompare(FlexL L, int (*compare)
  318.     (const void *D1, const void *D2))
  319. {
  320.     if (L)  {
  321.         L->compare = compare;
  322.         L->sorted = 0;
  323.         return 1;
  324.     }
  325.     return 0;
  326. }
  327.  
  328.  
  329. /*  FlexList stack and queue functions  */
  330.  
  331. void * FLpushN(FlexL L, FlexN N)
  332. {
  333.     if (!L || !N) 
  334.         return (void *) 0;
  335.     if (L->nodes >= L->maxNodes)  
  336.         return (void *) 0;
  337.     N->prev = FlexN0;
  338.     if ((N->next = L->front) != FlexN0)
  339.         N->next->prev = N;
  340.     else
  341.         L->rear = N;
  342.     L->front = N;
  343.     L->nodes++;
  344.     if (L->curNum) 
  345.         L->curNum++;
  346.     L->sorted = 0;
  347.     return N->data;
  348. }
  349.  
  350. void * FLpushD(FlexL L, const void *D)
  351. {
  352.     FlexN N;
  353.  
  354.     if (!L) 
  355.         return (void *) 0;
  356.     if (L->nodes >= L->maxNodes) 
  357.         return (void *) 0;
  358.     if (L->sizeofNode) {  /*  fixed size Fl